//原文链接：
//https://blog.csdn.net/ITSOK_123/article/details/124365398


//暴力枚举
bool repeatedSubstringPattern(string s) {
        int len = s.size();
        //枚举子串的长度
        for(int i=1;i<=len/2;i++){
            bool flag = true;
            //可以整除说明满足重复的前提
            if(len % i==0){
                for(int j=i;j<len;j++){
                    //如果是重复子串则必会循环
                    if(s[j]!=s[j-i]){
                     flag = false;
                     break;
                    }
                }
                if(flag) return true;
            }
        }
        return false;
    }
//KMP
class Solution {
public:
    //求next数组
    void getNext(int *next,const string &s){
            next[0]=0;
            int j=0;
            int len = s.size();
            for(int i=1;i<len;i++){
                while(j>0 && s[i]!=s[j]){
                    j=next[j-1];
                }
                if(s[i]==s[j]) j++;
                next[i]=j;
            }
        }
    //将问题转换为一般的求字符串匹配问题
    bool repeatedSubstringPattern(string s) {
        if(s.size()==0) return false;
        int len = s.size();
        int next[len];
        getNext(next,s);
        //重复子串的长度等于`len-next[len-1]`
        if(next[len-1]!=0 && len%(len-next[len-1])==0){
            return true;
        }
        return false;

    }
};

//库函数
//字符串`Str+Str`而言，我们去掉首元素进行查找Str的话，
//其查找的下标返回值必然会在原本的`Str+Str`的前半部分。
bool repeatedSubstringPattern(string s) {
        return (s+s).find(s,1)!= s.size();
    }
	

//也可以直接修改KMP算法实现来进行解题
class Solution {
public:
    bool kmp(const string& query, const string& pattern) {
        int n = query.size();
        int m = pattern.size();
		//这里采用不减一的next数组
        vector<int> fail(m, -1);
        for (int i = 1; i < m; ++i) {
            int j = fail[i - 1];
            while (j != -1 && pattern[j + 1] != pattern[i]) {
                j = fail[j];
            }
            if (pattern[j + 1] == pattern[i]) {
                fail[i] = j + 1;
            }
        }
        int match = -1;
		//掐头去尾查找是否存在模式串
        for (int i = 1; i < n - 1; ++i) {
            while (match != -1 && pattern[match + 1] != query[i]) {
                match = fail[match];
            }
            if (pattern[match + 1] == query[i]) {
                ++match;
                if (match == m - 1) {
                    return true;
                }
            }
        }
        return false;
    }

    bool repeatedSubstringPattern(string s) {
		//注意掐头去尾已经在KMP内部操作了
        return kmp(s + s, s);
    }
};
